// https://www.lintcode.com/problem/valid-perfect-square/

public class Solution {
    /**
     * @param num: a positive integer
     * @return: if num is a perfect square else False
     */
    public boolean isPerfectSquare(int num) {
        // write your code here
        long i = 0, j = num;
        while (i <= j) {
            long k = (long)((i + j) / 2); // int会溢出
            long k2 = k * k;
            if (k2 == num) {
                return true;
            } else if (k2 > num) {
                j = k - 1;
            } else {
                i = k + 1;
            }
        }
        return false;
    }
}